\documentclass[submission]{FPSAC2017}

\articlenumber{14}
\addbibresource{14_Hamaker_Keilthy_Patrias_Webster_Zhang_Zhou.bib}

\title{Shifted Hecke insertion and $K$-theory of $OG(n,2n{+}1)$}

\usepackage{amsfonts, amsbsy, latexsym, mathtools, ytableau, shuffle, multirow, mathdots, enumerate, tikz, comment, array}

\newtheorem{lem}{Lemma}
\newtheorem{theorem}{Theorem}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{cor}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{ex}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{defn}[theorem]{Definition}
\newtheorem*{defn*}{Definition}
\newtheorem*{thm*}{Theorem}
\newtheorem*{prop*}{Proposition}
\newtheorem*{cor*}{Corollary}
\newtheorem{fig}[theorem]{Figure}
\newtheorem{conjecture}[theorem]{Conjecture}

%Shortcuts for notation:
\def\Tab{P_{SK}}  
\def\rTab{Q_{SK}} 
\def\ksw{\hat{\equiv}}  
\def\pr{{^{\prime}}}
\def\row{\mathfrak{row}}
\def\D{\mathcal{D}}
\def\C{\mathcal{C}}
\def\std{\operatorname{std}}
\def\st{\mathfrak{st}}
\def\symfcn{K_{\lambda}}
\newcommand{\sss}{\scriptstyle}
\newcommand{\mw}{\mathcal{W}}
\newcommand{\ma}{\mathcal{A}}
\newcommand{\mo}{\mathcal{O}}
\newcommand{\md}{\mathcal{D}}
\newcommand{\ml}{\mathcal{L}}



\author[Hamaker, Keilthy, Patrias, Webster, Zhang, and Zhou]{Zachary Hamaker\thanks{Z.H. was supported by the Institute for Mathematics and its Applications with funds provided by the National Science Foundation.}\addressmark{1}, Adam Keilthy\addressmark{2}, Rebecca Patrias\thanks{All other authors were supported by RTG grant NSF/DMS-1148634.}\addressmark{3}, Lillian Webster\addressmark{4}, Yinuo Zhang\addressmark{5},\and Shuqi Zhou\addressmark{6}}


 
\address{\addressmark{1}Department of Mathematics, University of Michigan, Ann Arbor, MI \\ \addressmark{2}Mathematical Institute, University of Oxford, Oxford, UK \\ \addressmark{3}LaCIM, Universit\'e du Qu\'ebec \`a Montr\'eal, Montr\'eal, QC\\ \addressmark{4}Mathematics and Statistics Department, Grinnell College, Grinnell, IA\\
\addressmark{5}Department of Economics, Princeton University, Princeton, NJ \\
\addressmark{6}Department of Statistics, The Ohio State University, Columbus, OH}

\received{\today}

\abstract{Patrias and Pylyavskyy introduced shifted Hecke insertion as an application of their theory of dual filtered graphs. We show that shifted Hecke insertion has a natural place in the combinatorial study of the $K$-theory of the maximal orthogonal Grassmannian. In particular, we relate it to the $K$-theoretic jeu de taquin of Clifford-Thomas-Yong and use it to create new symmetric functions, which we use to derive a Littlewood-Richardson rule for the $K$-theory of the orthogonal Grassmannian equivalent to the rules of Clifford-Thomas-Yong and Buch-Samuel.}

\resume{
\begingroup\emergencystretch=1em
Patrias and Pylyavskyy ont introduit l'insertion de Hecke d\'ecal\'ee comme une application de leur th\'eorie des graphes filtr\'es en dualit\'e. Nous montrons que l'insertion de Hecke d\'ecal\'ee a une place naturelle dans l'\'etude combinatoire de la $K$-th\'eorie de $OG(n,2n+1)$. En particulier, nous la relions au jeu de taquin $K$-th\'eorique de Clifford-Thomas-Yong et nous l'utilisons pour cr\'eer de nouvelles fonctions sym\'etriques. Nous utilisons ces fonctions sym\'etriques pour d\'eriver une r\`egle de Littlewood-Richardson pour la $K$-th\'eorie de $OG(n,2n+1)$ qui est \'equivalente aux r\`egles de Clifford-Thomas-Yong et de Buch-Samuel.

\endgroup}
 
\keywords{symmetric functions, $K$-theory, insertion algorithms}


\begin{document}
\maketitle


\section{Introduction}


In~\cite{PPshifted}, Patrias and Pylyavskyy introduce shifted Hecke insertion as an application of their theory of dual filtered graphs.
It is a bijection between finite words in the positive integers and pairs $(\Tab,\rTab)$ of shifted tableaux of the same shape, where $\Tab$ is increasing and $\rTab$ is set-valued. 
We show that shifted Hecke insertion has a natural place in the combinatorial study of the $K$-theory for the orthogonal Grassmannian $OG(n,2n{+}1)$. 
In particular,  shifted Hecke insertion plays a role in $K$-theory of $OG(n, 2n + 1)$ similar to the role of (unshifted) Hecke insertion in the $K$-theory of the Grassmannian. 
Additionally, we highlight the role of shifted Hecke insertion as a tool for studying certain symmetric functions, similar to the relationship between RSK and Schur functions.
We next describe the setting and results in more detail.

The $K$-theory of the orthogonal Grassmannian $OG(n,2n{+}1)$  is well understood.
It has as a basis of Schubert structure sheaves indexed by shifted shapes, $\{\mo_\lambda\}$.
The product structure is determined by a combinatorial Littlewood-Richardson rule
\[
\mo_\lambda \cdot \mo_\mu = \sum_{\nu} (-1)^{|\nu| - |\lambda| - |\mu|} c^\nu_{\lambda, \mu} \mo_\nu
\]
first proven by Clifford, Thomas, and Yong~\cite{clifford2014k} using shifted $K$-theoretic jeu de taquin and a geometric Pieri rule of Buch and Ravikumar~\cite{buch2012pieri}. 
An analogous rule was presented by Buch and Samuel as the special case of a more general theory~\cite{BuchandSamuel2013}.
After identifying the equivariant $K$-theory of $OG(n,2n{+}1)$ with a ring consisting of polynomials, Ikeda and Naruse show the factorial Schur $P$-functions form a complete set of representatives~\cite{ikeda2013k}.
These can be specialized to the \emph{shifted stable Grothendieck polynomials} $GP_\lambda$, which are the image of each $\mo_\lambda$ under this identification.

The Littlewood-Richardson rule of Clifford, Thomas, and Yong is formulated in terms of \emph{shifted $K$-jeu de taquin}, a variant of jeu de taquin for \emph{increasing shifted tableaux}.
They use shifted $K$-jeu de taquin slides to define a map between increasing shifted skew tableaux and increasing shifted tableaux that we call \emph{shifted superstandard $K$-rectification}.
Identifying a word $w$ with the skew tableau $T_w$ whose entries lie on an anti-diagonal, we prove the following relationship.
\begin{theorem}
\label{t:rectification}
Let $w$ be a word and $P$ be the shifted superstandard $K$-rectification of $T_w$.
Then $\Tab(w) = P$ where $\Tab(w)$ is the shifted Hecke insertion tableau.
\end{theorem}

This is the shifted analogue of Theorem 4.2 of~\cite{ThomasYong}. 
As a consequence of \cref{t:rectification}, we can easily rephrase the Littlewood-Richardson rule of Clifford-Thomas-Yong in terms of shifted Hecke insertion as follows.

\begin{theorem}\label{t:Kstructure} The product structure for the $K$-theory of $OG(n,2n+1)$ is described by
\[
\mo_\lambda \cdot \mo_\mu = \sum_{\nu} (-1)^{|\nu| - |\lambda| - |\mu|} c^\nu_{\lambda, \mu} \mo_\nu,
\] where $c_{\lambda,\mu}^\nu$ is equal to the number of increasing shifted skew tableaux $R$ of shape $\nu/\lambda$ for which $P_{SK}(\row(R))$ is the minimal increasing tableau of shape $\mu$.
\end{theorem}

Another important consequence of \cref{t:rectification}  is that shifted Hecke insertion respects the \emph{weak $K$-Knuth equivalence} of Buch and Samuel~\cite{BuchandSamuel2013}.
More precisely, every word $u$ is weakly $K$-Knuth equivalent to the reading word of its shifted Hecke insertion tableaux $P_{SK}(u)$ (see \cref{insertionimplieskknuth}), so if $P_{SK}(u)=P_{SK}(v)$ then $u$ is weak $K$-Knuth equivalent to $v$. 
As with (unshifted) Hecke insertion, the converse is not true: one weak $K$-Knuth equivalence class may correspond to more than one insertion tableau.
In \cref{s:Klambda,s:LR}, we present an independent  proof of \cref{t:Kstructure} by using shifted Hecke insertion to study $GP_\lambda$ directly.
Here, we are using shifted Hecke insertion as a tool for the combinatorial study of symmetric functions, independent of the geometry.

For each shifted shape $\lambda$, we define the \emph{weak shifted stable Grothendieck polynomial} $K_\lambda$ as a generating function over multiset-valued shifted tableaux. 
We then show how to expand $K_\lambda$ in terms of the \emph{fundamental quasisymmetric functions} $f_\alpha$, which form a basis for the ring of quasisymmetric functions $\mbox{QSym}$ (see \cref{s:Klambda} for precise definitions).

\begin{theorem}\label{kisgood}
For any fixed increasing shifted tableau $T$ of shape $\lambda$,
\[K_\lambda = \sum_{\Tab(w) = T}f_{\D(w)},\] where $\D(w)$ is the descent set of the word $w$.
\end{theorem}

We show that the $K_\lambda$ are symmetric (\cref{p:symmetry}) and that they differ from Ikeda and Naruse's $GP_\lambda$ by a sign and change of variables (\cref{prop:Ikeda}). 
As a consequence, we see the product structure of $K_\lambda$, $GP_\lambda$, and $\mo_\lambda$ are identical, up to a predictable sign.

To understand this product structure at the level of symmetric functions, we define the shifted $K$-theoretic Poirier-Reutenauer algebra called $SKPR$ using weak $K$-Knuth equivalence. 
For any word $h$, we define elements $[[h]]=\sum_{w\ksw h} w$, where $\ksw$ denotes weak $K$-Knuth equivalence.
Multiplication is defined as the shuffle product. 
This generalizes the shifted Poirier-Reutenauer bialgebra of Jing and Li~\cite{JLshifted}, which is a shifted analogue of the Poirier-Reutenauer Hopf algebra~\cite{poirier1995algebres}. 
Our approach closely follows work of Patrias and Pylyavskyy on a $K$-theoretic Poirier-Reutenauer bialgebra~\cite{PPK}. 
Surprisingly, the shifted $K$-theoretic Poirier-Reutenauer algebra does not have the coalgebra structure found in the shifted Poirier-Reutenauer and $K$-theoretic Poirier Reutenauer bialgebras. 

We then construct an algebra homomorphism from $SKPR$ to QSym that we prove sends $[[h]]$ to a sum of $K_\lambda$ for any word $h$.


\begin{theorem}\label{mapisksum}
Letting $\lambda(T)$ denote the shape of $T$, we have
\[
\phi([[h]]) = \sum_{\row(T)\ksw h} K_{\lambda(T)}.
\]
\end{theorem} 

Using \cref{mapisksum}, we present a Littlewood-Richardson rule for $K_\lambda$. 
In light of our previous comments, this rule also applies to $GP_\lambda \cdot GP_\mu$ and $\mo_\lambda \cdot \mo_\mu$ and thus provides an independent proof of \cref{t:Kstructure}.
Our proof does not rely on Buch and Ravikumar's Pieri rule~\cite{buch2012pieri}. 

Proofs have been omitted for brevity but may be found in \cite{hamaker2015shifted}.

\section{Shifted Hecke Insertion and Weak $K$-Knuth Equivalence}\label{sec:Insertion}
 
We outline our argument that the shifted Hecke insertion given in \cite{PPshifted} respects the weak $K$-Knuth equivalence given in \cite{BuchandSamuel2013}. 
Before presenting our argument, we review previous work on increasing shifted tableaux, shifted Hecke insertion, and shifted $K$-jeu de taquin.

\subsection{Increasing shifted tableaux and shifted Hecke insertion}
To each strict partition $\lambda = (\lambda_1 > \lambda_2 > \ldots > \lambda_k)$ we associate the \emph{shifted shape}, which is an array of boxes where the $i$th row has $\lambda_i$ boxes and is indented $i-1$ units.
A \emph{shifted tableau} is a filling of the shifted shape with positive integers.
A shifted tableau is \emph{increasing} if the labels are strictly increasing from left to right along rows and top to bottom down columns. 
The \textit{reading word} of an increasing shifted tableau $T$, denoted $\row(T)$, is the word obtained by reading the entries left to right from the bottom row to the top row. The increasing shifted tableau below has reading word $8471367$.
\ytableausetup{boxsize=.35cm}
\begin{center}
\begin{ytableau}
\sss 1 & \sss 3 & \sss 6 & \sss 7 \\
\none & \sss 4 & \sss 7 \\
\none & \none & \sss 8 
\end{ytableau} \hspace{.5in} 
\end{center}


\begin{lem}\label{finitetableau}
There are finitely many increasing shifted tableaux filled with a given finite alphabet.
\end{lem}

We now briefly recall the rules for shifted Hecke insertion and refer the reader to \cite{PPshifted} for further reading. It is simultaneously a shifted analogue of Buch, Kresch, Shimozono, Tamvakis and Yong's Hecke insertion~\cite{HeckeInsertion} and a $K$-theoretic analogue of Sagan-Worley insertion, due independently to Sagan and Worley~\cite{sagan1987shifted, worley1984theory}. 
From this point on, ``insertion" will always refer to shifted Hecke insertion unless stated otherwise. 

First, we describe how to insert a positive integer $x$ into a given shifted increasing tableau $T$.
We start by inserting $x$ into the first row of $T$. 
For each insertion, we assign a box to record where the insertion terminates. 
This data will be used when we define the recording tableau.

The rules for inserting $x$ into a row or column of $T$ are as follows:
\begin{enumerate}
\item[(1)] If $x$ is weakly larger than all integers in the row (respectively column) and adjoining $x$ to the end of the row (respectively column) results in an increasing tableau $T'$, then $T'$ is the resulting tableau. 
We say the insertion terminates at the new box. 
\vspace{-.1in}
\item[(2)] If $x$ is weakly larger than all integers in the row (respectively column) and adjoining $x$ to the end of the row (respectively column) does not result in an increasing tableau, then $T' = T$. 
If $x$ is row inserted into a nonempty row, we say the insertion terminated at the box at the bottom of the column containing the rightmost box of this row. 
If $x$ is row inserted into an empty row, we say that the insertion terminated at the rightmost box of the previous row. 
If $x$ is column inserted into a nonempty column, we say the insertion terminated at the rightmost box of the row containing the bottom box of the column $x$ could not be added to. 

\iffalse
\textcolor{red}{column inserted into an empty column? I want to say that you never fail to insert into an empty column. If x fails to insert into an empty column, then x is equal to the top entry of the preceding column. If x was bumped from a diagonal, then would have to be strictly larger than the entry at the top of that column. If x was bumped via column insertion and x is equal to the top row in the previous column, then that must be the box that x can from.}
\fi
\end{enumerate}

For the next two rules, suppose the row (respectively column) contains a box with label strictly larger than $x$, and let $y$ be the smallest such label.
\begin{enumerate}
\item[(3)]If replacing $y$ with $x$ results in an increasing tableau, then replace $y$ with $x$. 
In this case, $y$ is the output integer for this step and is to be inserted in the next step.
If $x$ was inserted into a column or if $y$ was on the main diagonal, proceed to insert each future output integer into the next column to the right its column of origin.
If $x$ was inserted into a row and $y$ was not on the main diagonal, then insert $y$ into the row below.
\vspace{-.1in}
\item[(4)]If replacing $y$ with $x$ does not result in an increasing tableau, then do not change the entries of the row (respectively column). 
In this case, $y$ is the output integer. 
If $x$ was inserted into a column or if $y$ was on the main diagonal, proceed to insert each future output integer into the next column to the right its column of origin.
If $x$ was inserted into a row, then insert $y$ into the row below.
\end{enumerate}

For any given word $w = w_1w_2\cdots w_n$, we define the \textit{insertion tableau} $\Tab(w)$ of $w$ to be $(\cdots((\emptyset\xleftarrow{SK} w_1)\xleftarrow{SK} w_2)\cdots\xleftarrow{SK} w_n)$, where $\emptyset$ denotes the empty shape and $T \xleftarrow{SK} x$ denotes the insertion of the letter $x$ into the tableau $T$. See \cref{ex:word}.


In order to describe the recording tableau for shifted Hecke insertion of a word $w$, we need the following definition. 

\begin{defn}\cite{ikeda2013k}\label{def:setvaluedshifted} A \textit{set-valued shifted tableau} is defined to be a filling of the boxes of a shifted shape with finite, nonempty subsets of primed and unprimed positive integers with ordering $1'<1<2'<2<\ldots$ such that:

\begin{enumerate}
\item The smallest number in each box is greater than or equal to the largest number in the box directly to the left of it, if that box exists. \vspace{-.1in}
\item The smallest number in each box is greater than or equal to the largest number in the box directly above it, if that box exists. \vspace{-.1in}
\item There are no primed entries on the main diagonal. \vspace{-.1in}
\item Each unprimed integer appears in at most one box in each column, and each primed integer appears in at most one box in each row. 
\end{enumerate}
\end{defn}


A set-valued shifted tableau is called \textit{standard} if the set of labels is exactly $[n]$ for some $n$, each appearing either primed or unprimed exactly once. The \textit{recording tableau} of a word $w=w_1w_2\ldots w_n$, denoted  $\rTab(w)$, is a standard set-valued shifted tableau that records where the insertion of each letter of $w$ terminates. 
We define it inductively. 
 
Start with $\rTab(\emptyset) = \emptyset$. 
If the insertion of $w_k$ added a new box to $\Tab(w_1w_2\ldots w_{k-1})$, then add the same box  with label $k$ ($k\pr$ if this box was added by column insertion) to $\rTab(w_1w_2\ldots w_{k-1})$. 
If $w_k$ did not change the shape of $\Tab(w_1w_2\ldots w_{k-1})$, we obtain $\rTab(w_1w_2\ldots w_k)$ from $\rTab(w_1\ldots w_{k-1})$ by adding the label $k$ ($k\pr$ if it ended with column insertion) to the box where the insertion terminated. 
If insertion terminated when a letter failed to insert into an empty row, label the box where the insertion terminated $k\pr$.

\begin{ex}\label{ex:word}
Let $w = 451132$.  
We insert $w$ letter by letter, writing the insertion tableau at each step in the top row and the recording tableau at each step in the bottom row.  \\

\begin{center}
\ytableausetup{boxsize=1.3em}
\begin{ytableau}
\sss 4
\end{ytableau} \hspace{.15in}
\begin{ytableau}
\sss 4 & \sss 5 
\end{ytableau} \hspace{.15in}
\begin{ytableau}
\sss 1 & \sss 4 & \sss 5 
\end{ytableau} \hspace{.15in}
\begin{ytableau}
\sss 1 & \sss 4 & \sss 5 
\end{ytableau} \hspace{.15in}
\begin{ytableau}
\sss 1 & \sss 3 & \sss 5 \\
\none & \sss 4
\end{ytableau} \hspace{.15in}
\begin{ytableau}
\sss 1 & \sss 2 & \sss 4 & \sss 5 \\
\none & \sss 3
\end{ytableau}
$=\Tab(w)$ \\ 

\vspace{.05in}

\begin{ytableau}
\sss 1
\end{ytableau} \hspace{.15in}
\begin{ytableau}
\sss 1 & \sss 2 
\end{ytableau} \hspace{.15in}
\begin{ytableau}
\sss 1 & \sss 2 & \sss 3\pr 
\end{ytableau} \hspace{.15in}
\begin{ytableau}
\sss 1 & \sss 2 & \sss 3\pr 4\pr 
\end{ytableau} \hspace{.15in}
\begin{ytableau}
\sss 1 & \sss 2 & \sss 3\pr 4\pr \\
\none & \sss 5 
\end{ytableau} \hspace{.15in}
\begin{ytableau}
\sss 1 & \sss 2 & \sss 3\pr 4\pr & \sss 6\pr \\
\none & \sss 5
\end{ytableau}
$=\rTab(w)$ 
\end{center}
\end{ex}

\begin{theorem} \emph{\cite[Theorem~5.19]{PPshifted}}
\label{wordbijection}
The map $w \mapsto (\Tab(w),\rTab(w))$ is a bijection between words of positive integers and pairs of shifted tableaux $(P,Q)$ of the same shape where $P$ is an increasing shifted tableau and $Q$ is a standard set-valued shifted tableau.
\end{theorem}

\subsection{Weak $K$-Knuth equivalence and shifted jeu de taquin}
The Knuth relations determine which words have the same Robinson-Schensted-Knuth insertion tableau \cite[Theorem A1.1.4]{opac-b1096212}. 
We present Buch and Samuel's shifted $K$-theoretic analogue, called weak $K$-Knuth equivalence~\cite{BuchandSamuel2013}. 
As we will see in \cref{insertionimplieskknuth} and \cref{notURT}, weak $K$-Knuth equivalence is a necessary but not sufficient condition for two words to have the same shifted Hecke insertion tableau. 

\begin{defn}\cite[Definition~7.6]{BuchandSamuel2013}
\label{def:wkknuth} Define the \textit{weak $K$-Knuth equivalence relation} on the alphabet \{1,2,3,$\cdots$\}, denoted by $\ksw$, as the symmetric transitive closure of the following relations, where \textbf{u} and \textbf{v} are (possibly empty) words of positive integers, and  $a < b < c$ are distinct positive integers:
\[
\begin{array}{clcccl}
1. & (\textbf{u},a,a,\textbf{v}) \ksw (\textbf{u},a,\textbf{v}) & \ \hspace{1in}\ & & 4. & (\textbf{u},a,c,b,\textbf{v}) \ksw (\textbf{u},c,a,b,\textbf{v}) \\
2. & (\textbf{u},a,b,a,\textbf{v}) \ksw (\textbf{u},b,a,b,\textbf{v}) & & & 5. & (a,b,\textbf{u}) \ksw (b,a,\textbf{u}) \\
3. & (\textbf{u},b,a,c,\textbf{v}) \ksw (\textbf{u},b,c,a,\textbf{v}) 
\end{array} 
\]
\end{defn}

Two words $w$ and $w'$ are \emph{weak $K$-Knuth equivalent}, denoted $w\ \ksw \ w'$, if $w'$ can be obtained from $w$ by a finite sequence of weak $K$-Knuth equivalence relations.
Two shifted increasing tableaux $T$ and $T'$ are \emph{weak $K$-Knuth equivalent} if $\row(T)$ $\ksw$ $\row(T')$.

By removing relation (5), we obtain the $K$-Knuth relations of Buch and Samuel~\cite{BuchandSamuel2013}.
As in the $K$-Knuth equivalence but in contrast to Knuth equivalence, each weak $K$-Knuth equivalence class has infinitely many elements and contains words of arbitrary length. 


In \cite{clifford2014k}, Clifford, Thomas, and Yong create a shifted $K$-theoretic jeu de taquin algorithm for increasing shifted tableaux that is a natural analogue of the Thomas-Yong $K$-theoretic jeu de taquin \cite{ThomasYong} and of Sch\"utzenberger's jeu de taquin. We refer the reader to \cite{clifford2014k} for details. One important difference between Sch\"utzenberger's jeu de taquin and these $K$-theoretic analogues is that the order in which one performs the slides in the $K$-theoretic analogues may change the outcome of the procedure. In particular, a given skew tableau $T$ may rectify to more than one straight-shaped increasing shifted tableau depending on the \textit{rectification order}. We fix one such rectification order, which we call \textit{shifted superstandard rectification} for \cref{t:rectification} based on the \textit{superstandard tableaux} defined in \cref{sec:URT}.

For any word $w=w_1\ldots w_n$, let $T_w$ denote the shifted skew tableau consisting of $n$ boxes on the antidiagonal with reading word $w$. 
\cref{t:rectification} explains the relationship between shifted Hecke insertion and shifted $K$-jdt, affirming that shifted Hecke insertion is a $K$-theoretic analogue of Sagan-Worley insertion.
Our proof of \cref{t:rectification} relies on showing how a single insertion step replicates a sequence of $K$-jdt moves.
This requires a quite involved combinatorial argument, which we omit.



Using a result of Buch and Samuel~\cite{BuchandSamuel2013}, we can now relate shifted Hecke insertion to the weak $K$-Knuth relations.    
Tableaux $T$ and $T'$ are called \textit{jeu de taquin equivalent} if one can be obtained from another using shifted $K$-jdt. Their result says that weak $K$-Knuth equivalence and jeu de taquin equivalence are the same for increasing shifted tableaux. 
From this point on, we refer to both as ``equivalence.'' 

\begin{theorem}\cite[Theorem~7.8]{BuchandSamuel2013}
\label{jdt-equiv}
Let $T$ and $T\pr$ be increasing shifted tableaux. 
Then 
$\row(T)\ \ksw\ \row (T\pr)$
if and only if $T$ and $T\pr$ are jeu de taquin equivalent.  
\end{theorem}

\begin{cor}\label{insertionimplieskknuth}
We have $u \ \ksw \ \row(\Tab(u))$.
As a consequence, if $\Tab(u) = \Tab(v)$, then $u\  \ksw \ v$.  
\end{cor}

\begin{remark}\label{notURT}
The converse of the second part of \cref{insertionimplieskknuth} does not hold.  
Consider the words 12453 and 124533, which are easily seen to be weakly $K$-Knuth equivalent.  
We compute that shifted Hecke insertion gives the following distinct tableaux.
\[ \begin{array}{l c r}
\ytableausetup{boxsize=1em}
\Tab(12453) = 
\begin{ytableau}
\sss 1 & \sss 2 & \sss 3 & \sss 5 \\
\none & \sss 4
\end{ytableau}
& &
\Tab(124533) = 
\begin{ytableau}
\sss 1 & \sss 2 & \sss 3 & \sss 5 \\
\none & \sss 4 & \sss 5
\end{ytableau}
\end{array}\]
\end{remark}

\subsection{Unique Rectification Targets}\label{sec:URT}
As we have seen in \cref{notURT}, weak $K$-Knuth equivalence classes may have several corresponding insertion tableaux. 
This is a key difference between weak $K$-Knuth equivalence and the classical Knuth equivalence. 
Of particular importance in our setting are the classes of words with only one tableau. 


\begin{defn}\cite[Definition 3.5]{BuchandSamuel2013}
\label{def:urt}
An increasing shifted tableau $T$ is a \textit{unique rectification target}, or a URT, if it is the only tableau in its weak $K$-Knuth equivalence class.
Equivalently, $T$ is a URT if for every $w\ \ksw\ \row(T)$ we have $\Tab(w) = T$.  
If $\Tab(w)$ is a URT, we call the equivalence class of $w$ a \textit{unique rectification class}.  
\end{defn}

We refer the reader to \cite{BuchandSamuel2013, clifford2014k} for a more detailed discussion of URTs for shifted tableaux and straight shape tableaux. 
The tableaux given in \cref{notURT} are equivalent to each other, and hence neither is a URT.  

The \emph{minimal increasing shifted tableau} $M_\lambda$ of a shifted shape $\lambda$ is the tableau obtained by filling the boxes of $\lambda$ with the smallest values allowed in an increasing tableau. The \textit{superstandard shifted tableau} $S_\lambda$ of shifted shape $\lambda$ is obtained by filling the boxes in row $\lambda_i$ with $\lambda_1+\ldots+\lambda_{i-1}+1$ through  $\lambda_1+\ldots+\lambda_{i-1}+\lambda_i$.
 \ytableausetup{boxsize=1em}
\[\begin{array}{l r}
S_{(4,2)} = 
\begin{ytableau}
\sss 1 & \sss 2 & \sss 3 & \sss 4 \\
\none & \sss 5 & \sss 6
\end{ytableau} &
M_{(5, 2, 1)} = 
\begin{ytableau}
\sss 1 & \sss 2 & \sss 3 & \sss 4 & \sss 5 \\
\none & \sss 3 & \sss 4\\
\none & \none & \sss 5
\end{ytableau} 
\end{array}\]

In \cite[Corollary 7.2]{BuchandSamuel2013}, Buch and Samuel proved that minimal increasing shifted tableaux are URTs, and in \cite[Theorem 1.1]{clifford2014k}, Clifford, Thomas, and Yong show that superstandard tableaux are URTs.
As a consequence, we see there are URTs for every shifted shape.
Moreover, we can reformulate the Buch-Samuel and Clifford-Thomas-Yong rules using Hecke insertion. 
\begin{cor*}[\cref{t:Kstructure}]
\label{c:LR}
Let $T$ be a URT of shape $\lambda$.
The Littlewood-Richardson coefficient $c^\nu_{\lambda,\mu}$ for $K$-theory of $OG(n,2n+1)$ enumerates increasing shifted skew tableaux $R$ of shape $\nu/ \mu$ with $\Tab(\row(R)) = T_\lambda$ (up to sign).
\end{cor*}






\section{Weak shifted stable Grothendieck polynomials}
\label{s:Klambda}

We define the weak shifted stable Grothendieck polynomial $K_\lambda$ as a weighted generating function over weak set-valued shifted tableaux.

\begin{defn}\label{wsvst}
A \textit{weak set-valued shifted tableau} is a filling of the boxes of a shifted shape with finite, nonempty multisets of primed and unprimed positive integers with ordering $1\pr<1<2\pr<2<\cdots $ such that the conditions of \cref{def:setvaluedshifted} are satisfied.

\iffalse
\textcolor{red}{emphasize difference}
\begin{enumerate}
\item The smallest number in each box is greater than or equal to the largest number in the box directly to the left of it, if that box exists.\vspace{-.1in}
\item The smallest number in each box is greater than or equal to the largest number in the box directly above it, if that box exists.\vspace{-.1in}
\item There are no primed entries on the main diagonal. \vspace{-.1in}
\item Each unprimed integer appears in at most one box in each column, and each primed integer appears in at most one box in each row. 
\end{enumerate} 
\fi
\end{defn}
Note that the difference between set-valued shifted tableaux and weak set-valued shifted tableaux is that we allow multisets in the boxes of the latter. For example, the first and third tableaux in \cref{ex:Ktab} are weak set-valued but not set-valued shifted tableaux.

Given any weak set-valued shifted tableau $T$, we define $x^T$ to be the monomial $\prod_{i\geq 1}x_i^{a_i}$, where $a_i$ is the number of occurrences of $i$ and $i\pr$ in $T$.

\begin{defn}\label{k-lambda defn}
The \textit{weak shifted stable Grothendieck polynomial} is  
$K_\lambda = \sum_{T}x^T,$
where the sum is over the set of weak set-valued tableaux $T$ of shape $\lambda$. 
\end{defn}

\begin{remark}
Stable Grothendieck polynomials and their analogues typically have a sign $(-1)^{|T|-|\lambda|}$ for each monomial, where $|T|$ is the degree of $x^T$.
We suppress this sign for our definition $K_\lambda$ as others have done e.g.~\cite{lam2007combinatorial}.
It is easily reintroduced when necessary.

\end{remark}

\begin{ex}\label{ex:Ktab}We have $K_{(2,1)} = x_1^2x_2+2x_1x_2x_3+3x_1^2x_2^2+5x_1^2x_2x_3+5x_1x_2^2x_3+\cdots,$ where the coefficient of $x_1^2x_2^2$ is 3 because of the tableaux shown below. \begin{center}
\ytableausetup{boxsize=1.1em}
\begin{ytableau}
\sss 1 1 & \sss 2\pr\\
\none & \sss 2
\end{ytableau} \hspace{.8in}
\begin{ytableau}
\sss 1 & \sss 1 2\pr\\
\none & \sss 2
\end{ytableau} \hspace{.8in}
\begin{ytableau}
\sss 1 & \sss 1\\
\none & \sss 22
\end{ytableau}
\end{center}
Note that the lowest degree terms of $K_\lambda$ are a sum over shifted semistandard Young tableaux, so they form the Schur $P$-function $P_\lambda$.
\end{ex}





The weak shifted stable Grothendieck polynomial $K_\lambda$ is closely related to the shifted stable Grothendieck polynomial $GP_\lambda$ defined by Ikeda and Naruse in  \cite{ikeda2013k}. 
Here, 
$GP_\lambda = \sum_T (-1)^{|T|-|\lambda|} x^T,$
where we sum over all set-valued shifted tableaux $T$ of shape $\lambda$ (see \cref{def:setvaluedshifted}), $|T|$ is the degree of $x^T$, and $|\lambda|$ is the number of boxes in $\lambda$.
Given a set-valued tableau $T$, we may convert it to a multiset valued tableau by replacing each instance of $i$ or $i'$ with (potentially) multiple copies of that entry.
We now interpret this observation at the level of symmetric functions.

\begin{prop}\label{prop:Ikeda}  \textit{We have}
$ K_\lambda(x_1,x_2,\ldots)=(-1)^{|\lambda|} GP_\lambda \left (\frac{-x_1}{1-x_1},\frac{-x_2}{1-x_2},\ldots \right). $
\end{prop}


\subsection{The symmetry of $K_\lambda$}
From \cref{prop:Ikeda} and~\cite[Theorem 9.1]{ikeda2013k}, we can conclude that the weak shifted stable Grothendieck polynomial $K_\lambda$ is symmetric.
However, using shifted Hecke insertion, we provide a direct proof.
This also shows that $K_\lambda$ is a sum of stable Grothendieck polynomials. Moreover, by \cref{prop:Ikeda}, we obtain a new proof of symmetry for the $GP_\lambda$.
To our mind, this proof of symmetry is easier than the Ikeda-Naruse proof, as might be expected since their result follows as a consequence of symmetry for the more general factorial $K$-theoretic Schur $P$-functions.

We first write the $K_\lambda$ as a sum of quasisymmetric functions. To any $\D \subset [n-1]$, we associate the \emph{fundamental quasisymmetric function} $f_\D=\sum x_{i_1}\ldots x_{i_n}$, where $i_1\leq i_2\leq\cdots\leq i_n$ and $i_j<i_{j+1}$ if $j\in\D$.
The fundamental quasisymmetric functions form a basis for the \emph{ring of quasisymmetric functions} QSym, which is comprised of formal power series with bounded degree that are \emph{quasisymmetric}, i.e., the coefficients of $x^{\alpha_1}_1 \dots x^{\alpha_n}_n$ and $x^{\alpha_1}_{i_1} \dots x^{\alpha_n}_{i_n}$ are the same for any $i_1 < \dots < i_n$. 


The \emph{descent set} of a word $w = w_1w_2\ldots w_n$ is $\D(w) = \{i : w_i > w_{i+1}\}$. 
For example, $354211$ has descent set $\{2,3,4\}$. 
Similarly, the \emph{descent set} of a standard set-valued shifted tableau $T$ is
\[\D(T) =  
\left\lbrace \begin{array}{c c l}
\multirow{5}{*}{\textit{i}} &
\multirow{5}{*}{:} &
\text{both }i\text{ and }(i+1)\pr\text{ appear}\\
& & \qquad \textsc{ or } \\
& & i \text{ is strictly above } i+1 \\ 
& & \qquad \textsc{ or } \\
& &i\pr \text{ is weakly below } (i+1)\pr \text{ but not in the same box}
\end{array} \right\rbrace. \] 
The next result says that shifted Hecke insertion respects descent sets. 
Analogues of this result hold for many insertion algorithms, including RSK and Hecke insertion.
\begin{prop}
\label{thm:descent}
For any word $w=w_1w_2\ldots w_n$,
$\D(w) = \D(\rTab(w)).$
\end{prop}

By associating fundamental quasisymmetric functions to descent sets of words and applying \cref{thm:descent}, we can prove \cref{kisgood}.

A \emph{multiset-valued tableau} $T$ of ordinary (unshifted) shape satisfies conditions (1) and (2) of \cref{wsvst} and has no primed entries. In \cite{lam2007combinatorial}, Lam and Pylyavskyy define the \emph{weak stable Grothendieck polynomial}
$J_\mu = \sum_{T} x^T$
where the sum is now over multiset-valued tableaux. Note that our definition differs from theirs by taking the transpose.
Weak stable Grothendieck polynomials are symmetric functions.
Using Hecke insertion, each $J_\mu$ can be expressed as a sum over words instead of tableaux.
These words are equivalent under a subset of the weak $K$-Knuth relations, allowing us to express $K_\lambda$ in terms of weak stable Grothendieck polynomials, which gives the proposition below. From \cref{prop:Ikeda}, it also follows that $GP_\lambda$ is symmetric.
\begin{prop}
\label{p:symmetry}
For any shifted shape $\lambda$, $K_\lambda$ is symmetric. 
\end{prop}



\section{Shifted $K$-Poirier-Reutenauer Algebra and a Littlewood-Richardson rule}
\label{s:LR}
In \cite{poirier1995algebres}, Poirier and Reutenauer define a Hopf algebra spanned by the set of standard Young tableaux.
Jing and Li developed a shifted version~\cite{JLshifted}, and Patrias and Pylyavskyy developed a $K$-theoretic analogue~\cite{PPK}. 
In this section, we combine these approaches to introduce a shifted $K$-theoretic analogue.

We say a word $h$ is \textit{initial} if the letters appearing in it are exactly the numbers in $[k]$ for some positive integer $k$. 
For example, the words 54321 and 211345 are initial, but 2344 is not. For an initial word $h$, define $[[h]]$ to be the formal sum of words in the weak $K$-Knuth equivalence class of $h$:
$[[h]] = \sum_{h\ \ksw \ w} w.$  This is an infinite sum; however, the number of terms in $[[h]]$ of each length is finite.
For example, $[[213]] = 213 + 231 + 123 + 321 + 3221 + 3321 + 3211+ 32111 + \cdots .$ 
As a consequence of \cref{finitetableau}, the set of shifted Hecke insertion tableaux obtained by inserting the terms in $[[h]]$ is finite for any $h$. 
We define $SKPR$ to be the vector space over $\mathbb{R}$ spanned by these elements.


Let $\shuffle$ denote the usual shuffle product of words and  $w[n]$ be the word obtained from $w$ by increasing each letter by $[n]$. 
For example, if $w=312$, $w[4]=756$. 
Given words $h$ and $h\pr$ in alphabets $[n]$ and $[m]$, respectively, we define the product of their classes to be
\[
[[h]] \cdot [[h\pr]] = \sum_{w \ksw h, w\pr \ksw h\pr} w \shuffle w\pr[n].
\]
For example $[[12]]\cdot[[1]] = [[123]]+[[312]]+[[3123]].$
In general, $[[h]] \cdot [[h\pr]]$ can be expressed as a sum of classes.
\begin{prop}\label{productissum}
For any two initial words $h$ and $h\pr$, the product of their classes can be written as
\[
[[h]] \cdot [[h\pr]] = \sum_{h\pr\pr}\  [[h\pr\pr]],
\]
where the sum is over some finite set of initial words $h\pr\pr$.  
\end{prop}

It turns out that classes corresponding to URTs have particularly simple products, which we can express as an explicit sum over sets of tableaux as follows.

\begin{prop}\label{URTproduct}
Let $T_1$ and $T_2$ be two URTs. Then
\[
\left(\sum_{\Tab(u)= T_1} u\right)\cdot \left(\sum_{\Tab(v)= T_2}v\right)= \sum_{T\in \mathcal{T}(T_1\shuffle T_2)}\sum_{\Tab(w)=T}w,
\]
where $\mathcal{T}(T_1\shuffle T_2)$ is the finite set of shifted tableaux $T$ such that $T|_{[n]}=T_1$ and \\ $\Tab(\row(T)|_{[n+1,n+m]})=T_2$.
\end{prop}

Define $\phi:\ $SKPR$\to$ QSym by setting $\phi([[h]]) = \sum_{w\ksw h} f_{\D(w)}.$
The proof that this map is a homomorphism is straight-forward. 
Together with \cref{kisgood}, this implies \cref{mapisksum}.
Combined with \cref{URTproduct}, we can then prove a Littlewood-Richardson rule for $\symfcn$ independent of Buch and Ravikumar's Pieri rule.

\begin{theorem}\label{LR product}
Let $T$ be a URT of shape $\lambda$. Then we have $K_\lambda K_\mu = \sum_\nu c^\nu_{\lambda,\mu}K_\nu,$
where $c^\nu_{\lambda,\mu}$ is given by the number of increasing shifted skew tableaux $R$ of shape $\nu/\mu$ such that $\Tab(\row(R))=T$.
\end{theorem}


\acknowledgments{
This research was part of the 2015 REU program at the University of
Minnesota, Twin Cities, and was supported by RTG grant NSF/DMS-1148634. We thank Pasha Pylyavskyy, Vic Reiner, Takeshi Ikeda, Alex Yong, and the anonymous referees for helpful comments.


\begingroup\emergencystretch=.3em
\printbibliography
\endgroup


\end{document}
